package class05

type ComNode struct {
	Value int
	Left  *ComNode
	Right *ComNode
}

/*
	快速计算出完全二叉树的节点数量，要求复杂度小于O(N)

	国外刷题网站推荐：
		www.careercup.com

*/
func NodeNum(head *ComNode) int {
	return NodeNumProcess(head, 1, GetMaxHeight(head, 1))
}

func GetMaxHeight(node *ComNode, curLevel int) int {
	cur := node
	for cur != nil {
		cur = cur.Left
		curLevel++
	}

	return curLevel-1
}

func NodeNumProcess(node *ComNode, curLevel, h int) int {
	if curLevel == h {
		return 1
	}
	leftHeight := GetMaxHeight(node.Right, curLevel+1)
	if leftHeight == h {
		return 1<<(h-curLevel) + NodeNumProcess(node.Right, curLevel+1, h)
	} else {
		return 1<<(h-curLevel-1) + NodeNumProcess(node.Left, curLevel+1, h)
	}
}






















